package com.suanfa.bintree;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @author jukg
 * @date 2024/12/20 15:24
 * @description 深度优先遍历 需借助栈
 */
public class DeepTravers {

    public static void main(String[] args) {
        BinNodes root = buildNodes();
        Stack<BinNodes> stack = new Stack<>();
        stack.push(root);

        //深度遍历
        System.out.println("-----------深度优先遍历-------------");
        while(!stack.isEmpty()){
            BinNodes node = stack.pop();
            System.out.println(node.getName());

            if(node.getRight() !=null){
                stack.push(node.getRight());
            }
            if(node.getLeft()!= null){
                stack.push(node.getLeft());
            }
        }

        //广度优先遍历
        System.out.println("-----------广度优先遍历-------------");
        Queue<BinNodes> queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            BinNodes head =  queue.poll();
            System.out.println(head.getName());
            if(head.getLeft()!= null){
                queue.add(head.getLeft());
            }
            if(head.getRight()!= null){
                queue.add(head.getRight());
            }
        }
    }




    public static BinNodes buildNodes(){
        BinNodes A = new BinNodes("A");
        BinNodes B = new BinNodes("B");
        BinNodes C = new BinNodes("C");
        BinNodes D = new BinNodes("D");
        BinNodes E = new BinNodes("E");
        BinNodes F = new BinNodes("F");
        BinNodes G = new BinNodes("G");
        BinNodes H = new BinNodes("H");
        A.setLeft(B);A.setRight(C);
        B.setLeft(D);B.setRight(E);
        D.setLeft(H);
        C.setLeft(F);
        C.setRight(G);
        return A;
    }
}
